package week_08;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 151. 翻转字符串里的单词
 * 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
 * <p>
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 * <p>
 * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
 * <p>
 * 说明：
 * <p>
 * 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
 * 翻转后单词间应当仅用一个空格分隔。
 * 翻转后的字符串中不应包含额外的空格。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "the sky is blue"
 * 输出："blue is sky the"
 * 示例 2：
 * <p>
 * 输入：s = "  hello world  "
 * 输出："world hello"
 * 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
 * 示例 3：
 * <p>
 * 输入：s = "a good   example"
 * 输出："example good a"
 * 解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
 * 示例 4：
 * <p>
 * 输入：s = "  Bob    Loves  Alice   "
 * 输出："Alice Loves Bob"
 */
public class ReverseWords_151 {
    public String reverseWords(String s) {
        // 模块化 在每个过程标准化数据
        StringBuilder sb = new StringBuilder();
        // 1.去除开头结尾的空格 & 整理字符串
        trimSpaces(sb, s);
        // 2.反转整个字符串
        reverse(sb, 0, sb.length() - 1);
        System.out.println(sb.toString());
        // 3.遇到单词反转
        int start = 0;
        int end = 0;
        int n = sb.length();
        // 用for循环 会漏掉最后一个单词
        while (start < n) {
            // end 会停在空格
            //循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') end++;
            reverse(sb, start, end - 1);
            start = end + 1;
            end = end + 1;
        }
        return sb.toString();
    }

    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);

//            left++;
//            right--;
        }
    }

    public void trimSpaces(StringBuilder sb, String s) {
        // 去除前后空格 并 每个单词之间只插入一个空格
        char[] arr = s.toCharArray();
        int n = arr.length;
        int left = 0;
        while (left < n && arr[left] == ' ') left++;
        int right = n - 1;
        while (right >= 0 && arr[right] == ' ') right--;
        while (left <= right) {
            char ch = arr[left];
            // 在为字母和末尾不是空格的空格
            if (ch != ' ' || (ch == ' ' && sb.charAt(sb.length() - 1) != ' '))
                sb.append(arr[left]);
            left++;
        }
    }


    public String reverseWords1(String s) {
        // 使用api反转
        s = s.trim();
        List<String> words = Arrays.asList(s.split("\\s+"));
        Collections.reverse(words);
        return String.join(" ", words);

    }
}
